package tree.binarysearchtree;

import tree.TreeNode;

import java.util.Stack;

/**
 * @Classname : ValidateBinarySearchTree
 * @Description : 98. 验证二叉搜索树
 * https://leetcode.cn/problems/validate-binary-search-tree/
 * @Author : cty
 * @Date 2023/3/29 21:40
 */


public class ValidateBinarySearchTree {
    private Stack<Integer> stack;

    public boolean isValidBST(TreeNode root) {
        stack = new Stack<>();
        return inorder(root);
    }

    // 中序遍历
    private boolean inorder(TreeNode root) {
        if (root == null) return true;

        if (!inorder(root.left) || (!stack.isEmpty() && root.val <= stack.peek())) return false;
        stack.push(root.val);
        if (!inorder(root.right)) return false;
        return true;
    }

/*
    public boolean isValidBST(TreeNode root) {
        return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 递归迭代，分解子任务
    private boolean isValidBSTHelper(TreeNode root, long min, long max) {
        if (root == null) return true;

        if (root.val <= min || root.val >= max) return false;
        return isValidBSTHelper(root.left, min, root.val) && isValidBSTHelper(root.right, root.val, max);
    }
 */
}
